832D - Misha Grisha and Underground - CodeForces Solution

#include <bits/stdc++.h>

#define ll long long

#define pb push_back
#define el '\n'
#define pi 3.1415926536
#define mod 1000000007


#include <sstream>

#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
template<typename T>
using pbds = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;


ll const N = 1e6+4;
map<int, int> freqq;
map<int,int>mps2;
pair<int,int>p[N];


//priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<>>pq;
//priority_queue<ll,vector<ll>,greater<>>pq

int dx[] = { 1, -1,0, 0 };
int dy[] = { 0,0, -1,1  };
int disx[]={0,0,-1};
int disy[]={1,-1,0};
int chess_x[] = { -1,-1,1,1, 1, -1, 0, 0 };
int chess_y[] = { 1, -1,1,-1, 0,0, 1,-1 };
ll a[N];
ll mul(ll x, ll y)
{
    return ((x%mod) * (y%mod)) % mod;
}
ll add(ll x, ll y)
{
    return ((x%mod) + (y%mod)) % mod;
}
ll sub(ll x, ll y)
{
    return ((x%mod) - (y%mod)) % mod;
}
ll up[N][25],dpth[N];
vector<int>adj[N];
void dfs(int node){
    for(auto it:adj[node]){
        if(it==up[node][0])continue;
        dpth[it]=dpth[node]+1;
        up[it][0]=node;
        for(int i=1;i<24;i++){
            up[it][i]=up[up[it][i-1]][i-1];
        }
        dfs(it);
    }
}
int getLCA(int s,int f){
    if(dpth[s]<dpth[f])swap(s,f);
    int diff=dpth[s]-dpth[f];
    for(int i=0;i<24;i++){
        if(diff&(1<<i)){
            s=up[s][i];
        }
    }
    if(s==f){
        return s;
    }
    for(int i=24;i>=0;i--){
        if(up[s][i]!=up[f][i]){
            s=up[s][i],f=up[f][i];
        }
    }
    return up[s][0];
}
int getDIST(int s,int t,int f){
    int common1= getLCA(s,f),common2= getLCA(t,f),common3= getLCA(s,t);
    if(common1==common2){
       // cerr<<dpth[f]-dpth[common1]+(dpth[common3]-dpth[common2])+1<<el;
        return dpth[f]-dpth[common1]+(dpth[common3]-dpth[common2])+1;
    }
    return dpth[f]-max(dpth[common1],dpth[common2])+1;
}
int main(){
    fast;
    int n,q;cin>>n>>q;
    for(int i=1;i<=n-1;i++){
        int x;cin>>x;
        adj[i+1].pb(x);
        adj[x].pb(i+1);
    }
    dfs(1);
    while(q--){
       int a[3],ans=-1;
       cin>>a[0]>>a[1]>>a[2];
       sort(a,a+3);
       do{
           //a[0] for s, a[1] for t ,a[2] for f
           ans=max(ans,getDIST(a[0],a[1],a[2]));
       }while(next_permutation(a,a+3));
       cout<<ans<<el;
    }
    return 0;
}